package leetCode.secondWeek;

public class Code_50 {
  public double myPow(double x, int n) {
    switch (n) {
      case 0:
        return 1;
      case -1:
        return 1 / x;
      case 1:
        return x;
      case 2:
        return x * x;
      case -2:
        return 1 / x / x;
    }
    int base = 0, alter = 0, tmpN = n > 0 ? n : -n, minus = n > 0 ? 1 : -1;
    if (n < Integer.MIN_VALUE + 1) {
      tmpN = Integer.MAX_VALUE;
    }
    while (tmpN > 1) {
      base++;
      tmpN = tmpN / 2;
    }
    if (n < 0) {
      alter = (int) (n + myPow(2, base));
    } else {
      alter = (int) (n - myPow(2, base));
    }

    double twoCarry = myPow(x, minus * 2);
    while (--base > 0) {
      twoCarry = myPow(twoCarry, 2);
    }

    return myPow(x, alter) * twoCarry;
  }
}
